package ljl.alg.jianzhioffer.round2;

import java.util.Arrays;

/**
 * 直接放弃了，有阴影
 * */
public class _60_dice_possibilities {
    
    /**
     * 递归咋写？
     * 先抄一份，目前的功力写不出来
     *
     * 居然可以跑。。耗时 1760ms
     * 而 dp 版耗时 0ms
     *
     * */
    public double[] dicesProbability4(int n) {
        int[] prob = new int[5 * n + 1];
        prob6(n, prob);
        double[] res = new double[prob.length];
        double max = Math.pow(6, n);
        for (int i = 0; i < prob.length; i++)
            res[i] = prob[i] / max;
        return res;
    }
    
    void prob6(int num, int[] prob) {
        for (int i = 1; i <= 6 ; i++)
            prob(num, num, i, prob);
    }
    
    void prob(int origin, int cur, int sum, int[] prob) {
        if (cur == 1)
            prob[sum - origin]++;
        else
            for (int i = 1; i <= 6; i++)
                prob(origin, cur - 1, i + sum, prob);
    }
    
    /**
     * 动态规划
     * 感觉有点像九九乘法表
     * 比较难的那种乘法表
     * */
    public double[] dicesProbability(int n) {
        // 现在是 6 等会就不是了
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6);
        for (int i = 2; i <= n; i++) {
            double[] tmp = new double[5 * i + 1];
            for (int j = 0; j < dp.length; j++) {
                double inc = dp[j] / 6.0;
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += inc;
                }
            }
            dp = tmp;
        }
        return dp;
    }
}
